#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "sorts.h"
 
void merge_v1(ELE_TYPE arr1[], int len1, ELE_TYPE arr2[], int len2, ELE_TYPE *target)
{
	ELE_PTR p1,p2;
	ELE_PTR p1End,p2End;
 
	p1=arr1; p1End=arr1+len1;
	p2=arr2; p2End=arr2+len2;
 
	while ( p1<p1End && p2<p2End)
	{
		if ( *p1 <= *p2 )
			*target++ = *p1++;
		else 
			*target++ = *p2++;
	}
	
	while ( p1< p1End )
		*target++ = *p1++;
	
	while ( p2< p2End )
		*target++ = *p2++;
}
 
 
void merge_v2(ELE_TYPE arr1[], int len1, ELE_TYPE arr2[], int len2, ELE_TYPE *target)
{
	ELE_PTR  p1, p2, p1End, p2End;
	ELE_TYPE a, b, m1, m2;
 
	p1 = arr1;	p1End = arr1 + len1;
	p2 = arr2;	p2End = arr2 + len2;
	while ( p1<p1End && p2<p2End)
	{
		a = *p1;
		b = *p2;
 
		// if ( a>b) then m1=1, m2=0 else m1=0, m2=1
		m1 = (a < b);		
		m2 = (m1 ^ 1);
		p1 += m1;
		p2 += m2;
 
		*target++ = (m1 ? a : b);
	}
 
	while (p1< p1End)
		*target++ = *p1++;
 
	while (p2< p2End)
		*target++ = *p2++;
}

#ifdef _WIN32 
_declspec(naked)
	void merge_v2_asm(ELE_TYPE arr1[], int len1, ELE_TYPE arr2[], int len2, ELE_TYPE *target)
{
#define	_arr1  4
#define	_len1  8
#define	_arr2  12
#define	_len2   16
#define	_target	 20
 
#define	_OFS_P1END    0
#define	_OFS_P2END    4
#define	_ST_SIZE     24
 
#define	REG_p1	 esi
#define	REG_p2	 edi
#define	REG_TGT	 ebp
#define	REG_a	 eax
#define	REG_b	 ebx
 
#define	REG_M1  ecx
#define REG_M1L cl
#define	REG_M2  edx
 
	__asm
	{	
		push esi							;  save registers
		push edi
		push ebx
		push ebp
 
		sub  esp,(_ST_SIZE-16)
 
		mov  REG_p1, dword ptr [esp+_ST_SIZE+_arr1]
		mov  eax,    dword ptr [esp+_ST_SIZE+_len1]
		lea  edx,    [REG_p1+eax*4]
		mov  dword ptr [esp+_OFS_P1END], edx
 
		mov  REG_p2, dword ptr [esp+_ST_SIZE+_arr2]
		mov  eax,    dword ptr [esp+_ST_SIZE+_len2]
		lea  edx,    [REG_p2+eax*4]
		mov  dword ptr [esp+_OFS_P2END], edx
 
		mov  REG_TGT, dword ptr [esp+_ST_SIZE+_target]
		jmp  merge_v2_cmp
 
merge_v2_loop_start:
		xor  REG_M1, REG_M1			; REG_M1 = 0
 
		mov REG_a,  dword ptr [REG_p1]	 
		mov REG_b,  dword ptr [REG_p2]	
 
		cmp  REG_a, REG_b
		setl REG_M1L			   ; if a<b, then REG_M1 = 1
		cmovge REG_a, REG_b        ; if a >= b, then a = b
 
		mov REG_M2, REG_M1
		lea	REG_p1, DWORD PTR[REG_p1 + REG_M1 * 4]   ; if a<b, REG_p1++
		xor	REG_M2, 1               ; if a>=b, then REG_M2=1, else REG_M2=0
 
		mov	DWORD PTR[REG_TGT], REG_a       ; *target = a
		lea	REG_p2, DWORD PTR[REG_p2 + REG_M2 * 4]    ; if a>=b, REG_p2++
		add REG_TGT, 4              ; target++
 
merge_v2_cmp:
		cmp	REG_p1, DWORD PTR [esp+_OFS_P1END]
		jae	SHORT merge_v2_p1_tail_cmp
 
		cmp	REG_p2, DWORD PTR [esp+_OFS_P2END]
		jb	merge_v2_loop_start
		jmp  merge_v2_p1_tail_cmp
 
merge_v2_p1_tail_loop:
		mov	eax, DWORD PTR [REG_p1]
		mov	[REG_TGT], eax
		add	REG_p1, 4
		add	REG_TGT, 4
 
merge_v2_p1_tail_cmp:	
		cmp	REG_p1, DWORD PTR [esp+_OFS_P1END]
		jb	merge_v2_p1_tail_loop
 
		jmp merge_v2_p2_tail_cmp
 
merge_v2_p2_tail_loop:
		mov	eax, DWORD PTR [REG_p2]
		mov	[REG_TGT], eax
		add	REG_p2,  4
		add	REG_TGT, 4
 
merge_v2_p2_tail_cmp:	
		cmp	REG_p2, DWORD PTR [esp+_OFS_P2END]
		jb	merge_v2_p2_tail_loop
 
merge_v2_exit:
		add  esp, (_ST_SIZE-16)
 
		pop  ebp	;  restore registers
		pop  ebx
		pop  edi
		pop  esi
		ret
	}
}
#endif
 
void merge_sort_core(ELE_TYPE arr[], int len, ELE_TYPE *tBuff)
{
	int left_half;
	int right_half;
 
#if 0
	if ( len<=1)
		return ;
#else
	if (len <= INSERT_SORT_THRESHOLD)
	{
		insert_sort(arr, len);
		return ;
	}
#endif
	left_half  = (len+1)/2;
	right_half = len - left_half;
 
	merge_sort_core(arr,left_half, tBuff);
	merge_sort_core(arr+left_half, right_half, tBuff);
 
	memcpy(tBuff,arr,sizeof(ELE_TYPE)*left_half);
	merge_v1(tBuff, left_half, arr+left_half, right_half, arr);
	//merge_v2(tBuff, left_half, arr + left_half, right_half, arr);
	//merge_v2_asm(tBuff, left_half, arr+left_half, right_half, arr);
	
}
 
void merge_sort(ELE_TYPE arr[], int len)
{
	ELE_TYPE *tBuff= (ELE_TYPE*)malloc( sizeof(ELE_TYPE)*(len+1)/2);;
	merge_sort_core(arr,len, tBuff);
	free(tBuff);
}
 
 
void test_merge_sort()
{
	ELE_TYPE arr[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };
	int len = (int) sizeof(arr) / sizeof(arr[0]);
 
	printf("Original data are:");
	print_array(arr, len);
 
	merge_sort(arr, len);
	printf("The data after sorted are:");
	print_array(arr, len);	
}
